Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 12323 - Inspecting Radars / 12323.2.cpp
blob0d3d7c7904e248f649b448226d07f6f24ab41ec6
1 // Accepted
2 using namespace std;
3 #include <algorithm>
4 #include <iostream>
5 #include <iterator>
6 #include <numeric>
7 #include <sstream>
8 #include <fstream>
9 #include <cassert>
10 #include <climits>
11 #include <cstdlib>
12 #include <cstring>
13 #include <string>
14 #include <cstdio>
15 #include <vector>
16 #include <cmath>
17 #include <queue>
18 #include <deque>
19 #include <stack>
20 #include <list>
21 #include <map>
22 #include <set>
24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
26 #define D(x) cout << #x " is " << x << endl
28 typedef pair<int, int> point;
30 const int MAXN = 10000;
31 const int MAXR = 101;
32 const int MAXW = 720;
34 int mat[MAXR][MAXW];
35 int sum[MAXR][MAXW];
37 void precompute() {
38 for (int i = 0; i < MAXR; ++i) {
39 for (int j = 0; j < MAXW; ++j) {
40 sum[i][j] = mat[i][j];
41 if (i > 0) sum[i][j] += sum[i-1][j];
42 if (j > 0) sum[i][j] += sum[i][j-1];
43 if (i > 0 and j > 0) sum[i][j] -= sum[i-1][j-1];
48 int rectangle(int r1, int c1, int r2, int c2) {
49 int ans = sum[r2][c2];
50 if (r1 > 0) ans -= sum[r1-1][c2];
51 if (c1 > 0) ans -= sum[r2][c1-1];
52 if (r1 > 0 and c1 > 0) ans += sum[r1-1][c1-1];
53 return ans;
56 void solve(int height, int width) {
57 int ans = 0;
58 for (int i = 0; i + height < MAXR; ++i) {
59 for (int j = 0; j + width < MAXW; ++j) {
60 int option = rectangle(i, j, i + height, j + width);
61 if (option > ans) ans = option;
64 printf("%d\n", ans);
67 int main(){
68 int N, R;
69 while (scanf("%d %d", &N, &R) == 2) {
70 if (N == 0 and R == 0) break;
71 memset(mat, 0, sizeof mat);
73 for (int i = 0; i < N; ++i) {
74 int distance, angle;
75 scanf("%d %d", &distance, &angle);
76 mat[distance][angle]++;
77 mat[distance][angle + 360]++;
79 precompute();
81 int E;
82 scanf("%d", &E);
83 while (E--) {
84 int distance, angle;
85 scanf("%d %d", &distance, &angle);
86 solve(distance - 1, angle);
89 return 0;